using System;
using System.Text;

namespace DataStructure 
{
    class Array1<T>
    {
        private T[] _data; //数组存放的数据
        private int _size;      //实际数组存放元素的个数

        //构造函数，初始化数组的容量
        public Array1(int capacity)
        {
            _data = new T[capacity];
            _size = 0;
        }
        //无参数的构造函数(这里使用this复用带参的构造函数,默认传入参数10)
        public Array1(): this(capacity: 10) {}

        //返回Array数组长度
        public int Capacity => _data.Length;

        //访问Array数组元素个数
        public int Count => _size;
        //判断是否为空
        public bool IsEmpty => _size == 0;

        //判断后续对数组操作的索引是否越界
        private void CheckIndexRange(int index, int size)
        {
            if (index < 0 || index >= size)
            {
                throw new ArgumentException("数组索引越界");
            }
        }

        //增加数组的容量
        private void ResetCapacity(int newCapacity)
        {
            //newData用于存储未扩容数组的数据
            T[] newData = new T[newCapacity];
            //原数据拷贝到新的中
            for (int i = 0; i < _size; i++)
                newData[i] = _data[i];
            
            _data = newData;
        }

        //Add(在index位置插入元素t)
        public void Add(int index , T t)
        {
            CheckIndexRange(index,_size + 1); //判断索引是否越界
            
            if(_size == _data.Length)
                ResetCapacity(2* _data.Length);

            if (index == _size)
            {
                _data[index] = t;
            }
            else
            {
                //从数组的末尾开始，将所有大于等于index的元素向后移动一位
                for (int i = _size - 1; i > index; i--)
                {
                    _data[i] = _data[i - 1];
                }
                _data[index] = t;  //在index位置插入新元素

            }
            _size++;           //更新数组的实际大小
        }
        //依据Add方法实现的AddFirst/Last方法
        public void AddFirst(T t) => Add(index: 0, t);
        public void AddLast(T t) => Add(index: _size, t);
        
        //检查是否包含元素
        public bool Contains(T t)
        {
            for (int i = 0; i < _size; i++)
            {
                if (_data[i].Equals(t))
                    return true;
            }
            return false;
        }
        
        //返回数组元素的索引下标
        public int IndexOf(T t)
        {
            for (int i = 0; i < _size; i++)
            {
                if (_data[i].Equals(t))
                    return i;
            }
            return -1;
        }
        
        //删除指定索引元素
        public T RemoveIn(int index)
        {
            CheckIndexRange(index, _size);
            
            //记录被删除的元素
            T del = _data[index];
            //数组元素往前移
            for (int i = index + 1; i <= _size-1; i++)
                _data[i-1] = _data[i];
            _size--;
            
            _data[_size] = default(T) ?? throw new InvalidOperationException(); //将最后一个元素置为默认值
            
            //自动缩容
            if(_size == _data.Length/4)
                ResetCapacity(_data.Length/2);
                
            return del;
        }
        //依据RemoveIn方法实现的RemoveFirst/Last方法
        public T RemoveFirst() => RemoveIn(index: 0);
        public T RemoveLast() => RemoveIn(index: _size - 1);
        
        //删除指定元素
        public void Remove(T t)
        {
            //先找再删
            int index = IndexOf(t);
            if(index != -1)
                RemoveIn(index);
        }
        
        //获取数组元素(依据索引下标)
        public T Get(int index)
        {
            CheckIndexRange(index, _size);
            return _data[index];
        }
        //通过Get方法实现GetFirst和GetLast
        public T GetFirst() => Get(index: 0);
        public T GetLast() => Get(index: _size - 1);
        
        //修改(索引,新值)
        public void Set(int index, T t)
        {
            CheckIndexRange(index, _size);
            _data[index] = t;
        }
        
        //重写父类ToString方法用于打印测试输出
        public override string ToString()
        {
            StringBuilder res = new();
            //格式化
            res.Append(string.Format("MyArrayList: count={0} capacity={1}\n", _size, _data.Length));
            res.Append("[");
            for (int i = 0; i < _size; i++)
            {
                res.Append(_data[i]);
                if (i != _size - 1)
                    res.Append(", ");
            }
            res.Append("]");
            return res.ToString();
        }
    }
}